#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    const char* arr[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    void Combine(vector<string>& ret, int i, const string& digits, string Str)
    {
        if (i == digits.size())
        {
            ret.push_back(Str);
            return;
        }


        for (int j = 0; arr[digits[i] - '0'][j] != '\0'; j++)
        {
            Combine(ret, i + 1, digits, Str + arr[digits[i] - '0'][j]);
        }
    }

    vector<string> letterCombinations(const string& digits) {
        vector<string> ret;
        if (digits.empty())
        {
            return ret;
        }
        string Str;
        Combine(ret, 0, digits, Str);
        return ret;
    }
};

int main()
{
    string digits("258");
    int i = 0;
    vector<string> ret = Solution().letterCombinations(digits);
    for (auto e : ret)
    {
        cout << e << " ";
        i++;
    }
    cout << endl;
    cout << i << endl;
    return 0;
}